#include<iostream>
using namespace  std;

//对于queue容器了解就行，不用去模拟实现         queue：队列       deque：双端队列
//双端队列设计的初衷，是想要融合vector和list这两个容器的优点

//vector优点：能够通过下标随机访问，物理空间是连续的，尾插尾删效率高      （还有一个小点，cpu高速缓存命中率高）
//vector缺点：扩容容易造成空间的浪费，并且反复扩容效率低。头插头删效率低

//list优点：任意位置插入时间复杂度都是O(1),能够按需释放空间，不会造成空间的浪费
//list缺点：不能通过下标记性访问




//一、双端队列的思想
//1.用来存放数据的依然是数组，但是在存放元素的数组满了之后，并不去扩容，而是再去创建一个新的数组       ----这些数组暂时叫做存储数组
//2.每个存储数组的首元素的地址被放到一个专门存放指针的数组中去，这个数组也叫做-----中控数组




//3.双端队列就适合频繁的头插尾插数据的，偶尔下标访问的







//二、deque作为stack和queue的默认适配容器的优点
//stack   -deque对比用vector   deque优点：扩容代价不大，不需要拷贝数据，浪费空间也不多

//stack     -deque对比list     deque：cpu高速缓存命中率高，不会频繁的申请小块空间，申请和释放空间的次数少代价低


//queue     -deque对比list    deque优势：cpu高速缓存命中率高，不会频繁的申请小块空间，申请和释放空间的次数少代价低




//总结：也就是说作为默认容器是非常有优势的，但是高频访问用vector，高频中间位置插入用list